package src.algo.linkedlist_06;

import java.util.Scanner;

/**
 * @author zhikang.shu
 * @date 2021/8/19
 */
public class LRUBaseLinkedList<T> {

    private static final int DEFAULT_CAPACITY = 10;

    private int capacity;

    private SNode head;

    private int length;

    public LRUBaseLinkedList(int capacity) {
        this.capacity = capacity;
        this.length = 0;
        this.head = new SNode();
    }

    public LRUBaseLinkedList() {
        this.capacity = DEFAULT_CAPACITY;
        this.length = 0;
        this.head = new SNode();
    }

    public void add(T value) {
        SNode pre = findPreNode(value);
        if (pre == null) {
            if (length >= capacity) {
                removeTail();
            }
            insertHead(value);
        } else {
            deleteExistEle(pre);
            insertHead(value);
        }
    }

    public SNode findPreNode(T value) {
        if (head.next == null) {
            return null;
        }
        SNode node = head;
        while(node.next != null) {
            if (value.equals(node.next.value)) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    public void insertHead(T value) {
        SNode next = head.next;
        head.next = new SNode(value, next);
        length++;
    }

    public void deleteExistEle(SNode pre) {
        SNode node = pre.next;
        pre.next = node.next;
        node.next = null;
        length--;
    }

    public void removeTail() {
        SNode node = head;
        if (node.next == null) {
            return;
        }
        while(node.next.next != null) {
            node = node.next;
        }
        node.next = null;
        length--;
    }

    private void printAll() {
        SNode node = head.next;
        while (node != null) {
            System.out.print(node.value + ",");
            node = node.next;
        }
        System.out.println();
    }


    public static void main(String[] args) {
        LRUBaseLinkedList list = new LRUBaseLinkedList(5);
        Scanner sc = new Scanner(System.in);
        while (true) {
            list.add(sc.nextInt());
            list.printAll();
        }
    }
}






class SNode<T> {

    public T value;

    public SNode next;

    public SNode() {
    }


    public SNode(T value, SNode next) {
        this.value = value;
        this.next = next;
    }
}